Generally, when compiling the source code of a program written in a programming language, the program is optimized in order to increase the execution speed attained by a computer.
Various optimization methods are available. As one optimization method, on the assumption that the parallel execution of instructions is performed by a processor such as a CPU that is compatible with the architecture of the IA-64 produced by Intel Corp. and Hewlett Packard Corp., the order of instructions is changed for a code scheduling process that extracts parallelisms, so that as many instructions as possible can be issued in parallel.
However, in a program, various restrictions may be placed on the changing of the order of instructions, and only a limited code scheduling function may be available. Although the restrictions imposed in such a case include those associated with control, memory access and exceptions, a hardware support mechanism is available and practically employed that reduces the effects of the control and memory access restrictions. As yet, however, no hardware support mechanism has been implemented that reduces the effects arising from exception restrictions.
When parallelisms are extracted as instructions from the code of a program, exceptions generated by preceding instructions must be processed. According to a specific conventional method employed for this processing, exceptions generated by instructions are not immediately executed. Instead, whether exceptions have occurred is determined at locations whereat instructions were originally located in the program prior to optimization, and then, processing of the actual exceptions is performed. Therefore, exception generative instructions can be performed in advance, while original context is maintained at the sites at which exceptions occurred.
Since an instruction that may generate an exception is speculatively executed and a parallelism is extracted, the conventional technique has assumed hardware support for the restriction of an exception (hereinafter referred to as a speculative exception) that occurs due to an exception generative instruction that is speculatively executed. This type of conventional technique is disclosed, for example, in document 1 “Sentinel Scheduling: A Model For Compiler-Controlled Speculative Execution”, Scott A Mahlke, William Y. Chen, Roger A. Bringmann, Rechard E. Hank, Wen-Mei W. Hwu, B. Ramkrishna Rau and Michael S. Schlansker, ACM Transactions On Computer Systems, Vol. 11, No. 4, November 1993, pp. 376-408.
In document 1, a method is proposed whereby, under hardware support, a compiler speculatively moves an instruction and generates compensation code when an exception has occurred. In the hardware assumed here, for a speculative instruction, a special value is obtained through the calculation, instead of the occurrence, of an exception. Thereafter, this special value is transiently transmitted by a succeeding speculative instruction and a non-speculative instruction generates an exception when it is employed. An instruction for determining whether an exception has actually occurred is called a sentinel instruction.
According to this conventional technique, the exception generative instruction is speculatively scheduled in the following manner.    1. The last instruction that employs a generated value (potential sentinel instruction) is obtained for each exception generative instruction.    2. List scheduling is used to obtain the earliest execution time for each instruction. When an exception generative instruction is scheduled beyond the branch, side effects (writing to memory) and another exception generative instruction, the pertinent instruction is speculative. Therefore, as needed, an explicit sentinel instruction is generated using the information obtained at step 1.    3. When software is employed for recovery from the exception state, compensation code is generated for a handler when an exception corresponding to each sentinel instruction has occurred.
Furthermore, another conventional technique of this type is disclosed in Japanese Unexamined Patent Publication No. Hei 12-020320. According to the technique disclosed in this publication, speculative execution of an exception generative instruction is implemented by a compiler and with the support of a run-time library.
This conventional technique speculatively executes an exception generative instruction in the following manner.    1. A compiler registers, as an interrupt inhibited interval, a final portion of generated object code wherein the execution order of instructions is changed from the original programmed order by the speculative execution of an exception generative instruction.    2. When an exception has occurred, an exception handler dynamically generates and executes compensation code based on the interrupt inhibited interval information.
[Problems to be Solved by the Invention]
As is described above, a variety of restrictions are placed on code scheduling when program instructions are executed in parallel, and no special mechanism for reducing these restrictions for exceptions is implemented under restriction hardware support. Whereas, in a language, such as Java, in which strict handling of exceptions is necessary, restrictions existing between exception generative instructions greatly affect the extraction of parallelisms for program instructions. Thus, it is difficult for a compiler to extract parallelisms for instructions from a program that is written in a language, such as the Java, in which the strict handling of exceptions is a requirement.
A more detailed explanation will be given using the Java language. The specifications for the Java language define the strict handling of exception conditions that occur during the execution of a program. An exception state defined by a system (a case wherein a null object pointer is used, a case wherein an access is issued with a subscript that exceeds the length of an array, or a case wherein the division of an integer by 0 is attempted) or an exception state defined by a user can be detected during the execution of a program, and can be processed by a user defined exception handler. Then, when the execution of the handler has been completed, program control exits the area wherein the exception was detected.
Since the control flow is changed by the occurrence of an exception, an overall order is maintained between the occurrence of side effects (the element and the class of an array or the writing of an object to a field) in a program and the generation of an exception. That is, to execute a user defined exception handler, the following two program conditions must be satisfied.    1. All side effects occurring before the appearance of an exception must be observed.    2. No side effects occurring after the appearance of an exception must be observed.
In Java, basic operations, such as the reading and the writing of the elements of an array and of an object to a field, are accompanied by the occurrence of an exception during the execution of a program. That is, when a Java program is complied and Java instructions are translated into machine language instructions, basic operation statements are transformed into instructions for detecting exceptions and into memory access or calculation process for performing the actual operations. Memory access and calculation processes may appear exceptions. An exception generated here is a processor (hardware) state that is the result of an access violation, or of a divide overflow produced by an attempt to divide by 0. Another exception that may accompany the execution of a program is a program execution state precipitated by the inclusion of data that does not conform to the specifications of the programming language. In the following explanation, when the first exception must be specifically distinguished from other exceptions, this is called a hardware exception. A hardware exception occurs when the correct execution of a machine language program can not be continued because a program error has occurred, a processor has read data from or written data to an incorrect memory area, or the execution of an impossible calculation has been attempted. Other exceptions are those defined as error processes by a programming language, or a program, when due to a user error during the writing of a program an element that exceeds the size of an array is read or written or an incorrect input value is supplied for a function.
To avoid the occurrence of hardware exceptions, restrictions are placed on the code scheduling order for instructions for performing side effects, instructions for detecting the occurrence of an exception and generative instructions for exceptions. Since accesses of array elements and of field variables, both of which are accompanied by restrictions that are imposed on order execution, frequently appear in a Java program, for code scheduling, these restrictions greatly interfere with the process for extracting parallelisms for instructions.
In addition, as is described above, an exception that is generated by a previously issued instruction must be processed when the parallelism of an instruction for a program is extracted. Conventionally, an exception that is generated by an instruction is not immediately performed, and instead, whether or not the exception occurred is determined at the original location, before optimization, of the instruction in the program, and then the actual exception process is performed.
In this case, however, the cost of determining for an instruction whether an exception was previously generated can not be ignored. For the above IA-64, for example, special machine language code for detecting a speculative exception must be prepared, and when the instruction is greatly displaced, it is easy to understand that the program execution speed will be greatly affected by the instruction to ascertain whether an exception occurred.
The conventional technique described in reference 1 can speculatively execute an instruction that may generate a hardware exception, but the order restrictions still remain between an instruction including side effects and an instruction for detecting the occurrence of an exception. In order to speculatively execute an instruction for providing side effects, a hardware cost is imposed when writing to memory is canceled.
In addition, since hardware support is required, this conventional technique can not be used directly for a common processor lacking the requisite hardware for the speculative execution of an instruction.
Furthermore, it is not practical to employ software to emulate the conventional method because of the high cost that is imposed for additional instructions. Therefore, in this conventional technique, the overhead is increased merely by the speculative execution of hardware exception generative instructions and by the use of a model for the recovery from the exception state. And the technique can not satisfactorily reduce the order restrictions imposed on the exception generative instructions of the compiler for the Java language.
The conventional technique described in Japanese Unexamined Patent Publication No. Hei 12-020320 can be implemented without any additional software overhead when an exception does not occur. However, since compensation code is generated by the exception handler during the execution of the program, only after all machine language instruction sequence have been determined is this technique employed for optimization, i.e., only after the allocation of registers for the optimization of the code scheduling. Thus, parallelisms due to the speculative execution of the exception generative instructions can not be employed for an optimization process that is accompanied by code transformation.
It is, therefore, one object of the present invention to employ software for the reduction of the preceding restrictions imposed on an exception generative instruction for another instruction, so that program instruction parallelisms, including exception generative instructions, can effectively be obtained.